from tools.treeNode import Tree


# 思路：
# 1. 求两个叶子节点之间的路径长度
# 两个叶子节点之间路径 = 根节点左右儿子的深度之和
# 2. 计算节点的深度：距离叶子节点的深度
class Solution(object):

    def diameterOfBinaryTree(self, root):
        self.ans = 1
        self.depth(root)
        # 经过节点数-1
        return self.ans - 1

    def depth(self, node):
        # 访问到空节点了，返回0
        if not node:
            return 0
        # 左儿子为根的子树的深度
        L = self.depth(node.left)
        # 右儿子为根的子树的深度
        R = self.depth(node.right)
        # 计算d_node即L+R+1 并更新ans
        self.ans = max(self.ans, L + R + 1)
        # 返回该节点为根的子树的深度
        return max(L, R) + 1


root = Tree(1)
root.left = Tree(2)
root.right = Tree(3)
root.left.left = Tree(4)
root.left.right = Tree(5)
root.right.left = Tree(6)
root.right.right = Tree(7)
print(Solution().diameterOfBinaryTree(root))
